Celestin Apprentice 7/Apprentice-Release7.iso/Environments/Small Eiffel 0.4.8/lib_std/collection.e

Text File | 1997-04-13 | 9.7 KB | 461 lines | [TEXT/ttxt]

-- Part of SmallEiffel -- Read DISCLAIMER file -- Copyright (C)
-- Dominique COLNET and Suzanne COLLIN -- [e-mail]
--
deferred class COLLECTION[E]
--
-- Common abstract definition of a sequentiable collection of
-- objects. Such a collection is traversable using a simple
-- INTEGER index from `lower' to `upper'. Items can be added,
-- changed or removed.
--
-- The SmallEiffel standard library (lib_std) provides four
-- implementations : ARRAY[E], FIXED_ARRAY[E], LINK_LIST[E]
-- and LINK2_list[E]. All implementations have exactly the
-- same behavior. Switching from one implementation to another
-- only change the memory used and the execution time.
--

inherit
   ANY
      undefine copy, is_equal
      redefine fill_tagged_out_memory
      end;

feature -- Indexing :

   lower: INTEGER is
     -- Lower index bound.
      deferred
      end;

   upper: INTEGER is
     -- Upper index bound.
      deferred
      end;

   frozen valid_index(index: INTEGER): BOOLEAN is
     -- True when `index' is valid (ie. inside actual
     -- bounds of the collection).
      do
     Result := lower <= index and then index <= upper;
      ensure
     Result = (lower <= index and index <= upper);
      end;

feature -- Counting :

   count: INTEGER is
     -- Number of elements actually stored in the collection.
      deferred
      ensure
     Result = upper - lower + 1
      end;

   empty: BOOLEAN is
     -- Is collection empty?
      do
     Result := (count = 0);
      end;

feature -- Accessing :

   item, infix "@" (index: INTEGER): E is
     -- Item at position `index'.
      require
     valid_index(index)
      deferred
      end;

   first: like item is
      require
     count >= 1
      do
     Result := item(lower);
      end;

   last: like item is
      require
     count >= 1
      do
     Result := item(upper);
      end;

feature -- Writing :

   put(element: like item; index: INTEGER) is
     -- Put `element' at position `index'.
      require
     valid_index(index)
      deferred
      ensure
     item(index) = element;
     count = old count
      end;

   swap(i1, i2: INTEGER) is
      require
     valid_index(i1);
     valid_index(i2)
      local
     tmp: like item;
      do
     tmp := item(i1);
     put(item(i2),i1);
     put(tmp,i2);
      ensure
     item(i1) = old item(i2);
     item(i2) = old item(i1);
     count = old count
      end;

   set_all_with(v: like item) is
     -- Set all item with value `v'.
      deferred
      ensure
     count = old count
      end;

   set_slice_with(v: like item; lower_index, upper_index: INTEGER) is
     -- Set all item with `v'.
      require
     lower_index <= upper_index;
     valid_index(lower_index);
     valid_index(upper_index)
      local
     i: INTEGER;
      do
     from
        i := lower_index;
     until
        i > upper_index
     loop
        put(v,i);
        i := i + 1;
     end;
      ensure
     count = old count
      end;

   clear_all is
     -- Set all items to default values.
      local
     value: like item;
      do
     set_all_with(value);
      ensure
     count = old count;
     all_cleared
      end;

feature -- Adding :

   add_first(element: like item) is
      deferred
      ensure
     first = element;
     count = 1 + old count;
     lower = old lower;
     upper = 1 + old upper
      end;

   add_last(element: like item) is
      deferred
      ensure
     last = element;
     count = 1 + old count;
     lower = old lower;
     upper = 1 + old upper
      end;

   add(element: like item; index: INTEGER) is
     -- Add `element' at rank `index'.
     -- Range [`index' .. `upper'] is translated by 1 to
     -- the right and then, `element' is written at `index'.
      require
     lower <= index;
         index <= upper + 1
      deferred
      ensure
     item(index) = element;
         count = 1 + old count;
     upper = 1 + old upper
      end;

feature -- Modification :

   force(element: E; index: INTEGER) is
     -- Put `element' at position `index'. Collection is
     -- resized if `index' is not inside current bounds.
     -- New bounds are initialized with default values.
      require
     index >= lower
      deferred
      ensure
     valid_index(index);
     item(index) = element
      end;

   from_collection(model: COLLECTION[like item]) is
      -- Initialize the current object with the contents of `model'.
      require
     model /= Void
      deferred
      ensure
     count = model.count;
      end;

feature -- Removing :

   remove_first is
     -- Remove the first element of the collection.
     -- Indexing
      require
     not empty
      deferred
      ensure
     count = (old count) - 1;
         (lower = (old lower) + 1) xor (upper = (old upper) - 1)
      end;

   remove(index: INTEGER) is
     -- Remove one element at position `index'. Followings
     -- elements (after `index') are moved one position left.
      require
     valid_index(index)
      deferred
      ensure
     count = (old count) - 1;
     upper = (old upper) - 1;
      end;

   remove_last is
      require
     not empty;
      deferred
      ensure
     count = (old count) - 1;
     upper = (old upper) - 1
      end;

   clear is
     -- Discard all items.
      deferred
      ensure
     empty;
      end;

feature -- Looking and Searching :

   has(x: like item): BOOLEAN is
     -- Look for `x' using `equal' for comparison.
      do
     if count > 0 then
        Result := index_of(x) <= upper;
     end;
      end;

   fast_has(x: like item): BOOLEAN is
     -- Same as `has' but use `=' for comparison.
      do
     if count > 0 then
        Result := fast_index_of(x) <= upper;
     end;
      end;

   index_of(element: like item): INTEGER is
     -- Give the index of the first occurrence of `element' using
     -- `is_equal' for comparison.
     -- Answer `upper + 1' when `element' is not inside.
      deferred
      ensure
     lower <= Result;
     Result <= upper + 1;
     Result <= upper implies equal(element,item(Result));
      end;

   fast_index_of(element: like item): INTEGER is
     -- Same as `index_of' but use `=' for comparison.
      deferred
      ensure
     lower <= Result;
     Result <= upper + 1;
     Result <= upper implies element = item(Result);
      end;

feature -- Looking and comparison :

   all_cleared: BOOLEAN is
     -- Are all items set to default values?
      deferred
      end;

   nb_occurrences(element: like item): INTEGER is
     -- Number of occurrences using `equal'.
     -- See also `fast_nb_occurrences' to chose
     -- the apropriate one.
      deferred
      ensure
     Result >= 0
      end;

   fast_nb_occurrences(element: like item): INTEGER is
     -- Number of occurrences using `='.
      deferred
      ensure
     Result >= 0;
      end;

feature -- Printing :

   fill_tagged_out_memory is
      local
     i: INTEGER;
     v: like item;
      do
     tagged_out_memory.append("lower: ");
     lower.append_in(tagged_out_memory);
     tagged_out_memory.append(" upper: ");
     upper.append_in(tagged_out_memory);
     tagged_out_memory.append(" [");
     from
        i := lower;
     until
        i > upper or else tagged_out_memory.count > 2048
     loop
        v := item(i);
        if v = Void then
           tagged_out_memory.append("Void");
        else
           v.out_in_tagged_out_memory;
        end;
        if i < upper then
           tagged_out_memory.extend(' ');
        end;
        i := i + 1;
     end;
     if i <= upper then
        tagged_out_memory.append(" ...");
     end;
     tagged_out_memory.extend(']');
      end;

feature -- Other Features :

   replace_all(x, r: like item) is
      local
     i: INTEGER;
      do
     from
        i := lower;
     until
        i > upper
     loop
        if equal_like(item(i),x) then
           put(r,i);
        end;
        i := i + 1;
     end;
      end;

   fast_replace_all(x, r: like item) is
      local
     i: INTEGER;
      do
     from
        i := lower;
     until
        i > upper
     loop
        if item(i) = x then
           put(r, i);
        end;
        i := i + 1;
     end;
      end;

   move(lower_index, upper_index, distance: INTEGER) is
     -- Move range `lower_index' .. `upper_index' by `distance'
     -- positions. Negative distance moves towards lower indices.
     -- Free places get default values.
      require
     lower_index <= upper_index;
     valid_index(lower_index);
     valid_index(lower_index + distance);
     valid_index(upper_index);
     valid_index(upper_index + distance)
      local
     default_value: like item;
     i: INTEGER;
      do
     if distance = 0 then
     elseif distance < 0 then
        from
           i := lower_index;
        until
           i > upper_index
        loop
           put(item(i),i + distance);
           put(default_value,i);
           i := i + 1;
        end;
     else
        from
           i := upper_index;
        until
           i < lower_index
        loop
           put(item(i),i + distance);
           put(default_value,i);
           i := i - 1;
        end;
     end;
      ensure
     count = old count
      end;

   slice(low, up: INTEGER): like Current is
     -- Create a new collection initialized with elements of
     -- range `low'..`up'. Result has the same dynamic type
     -- as Current collection. The `lower' index of the new
     -- collection is the same as `lower' of Current.
      require
     valid_index(low);
     valid_index(up);
     low <= up
      deferred
      ensure
     same_type(Result);
     Result.count = up - low + 1;
     Result.lower = lower
      end;

feature -- The Guru section :

   free is
     -- Free the memory used by the Current COLLECTION (objects
     -- pointed by the Current COLLECTION are not affected).
     -- Assume you don't use Current any more.
      deferred
      end;

feature {NONE}

   frozen equal_like(e1, e2: like item): BOOLEAN is
     -- Note: this feature is called to avoid calling `equal'
     -- on expanded types (no automatic conversion to
     -- corresponding reference type).
      do
     if e1.is_basic_expanded_type then
        Result := e1 = e2;
     elseif e1.is_expanded_type then
        Result := e1.is_equal(e2);
     elseif e1 = e2 then
        Result := true;
     elseif e1 = Void or else e2 = Void then
     else
        Result := e1.is_equal(e2);
     end;
      end;

end -- COLLECTION[E}